975C - Valhalla Siege - CodeForces Solution

binary search *1400

Please click on ads to support us..

Python Code: 

import bisect
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

n, q = map(int, input().split())
a = list(map(int, input().split()))
k = list(map(int, input().split()))
s = [0]
for i in a:
    s.append(s[-1] + i)
ans = []
u = 0
for i in k:
    u += i
    x = bisect.bisect_right(s, u)
    ans0 = n - x + 1
    if not ans0:
        ans0, u = n, 0
    ans.append(ans0)
sys.stdout.write("\n".join(map(str, ans)))

C++ Code: 

#include<bits/stdc++.h>
using namespace std;
using ll = long long int ;
int upperbound(long long int x, vector<long long int > & cum) {
	int low = 0 , high = (int)cum.size() ;
	
	while(low < high){
		int mid = (low + high ) >> 1;
		if( x >= cum[mid] ) low = mid + 1;
		else high = mid ;
	}
	return low ;
}
 
 
int main()
{
	int n , q ;
	scanf("%d%d",&n,&q);
	
	vector<int> strength(n);
	vector<long long int > arrows(q),cum(n+1);
 
	
	for(auto &x : strength ) scanf("%d",&x);
	for(auto &x : arrows ) scanf("%lld",&x);
	
	for(int i = 1 ; i <= n; i++){
		cum[i] = cum[i-1] + strength[i-1] ;
	}
 
	ll last = 0;
	for(long long int x : arrows){
		x += last ;
		
		int ind = upperbound(x,cum);
		if(ind > n ){
			last = 0;
			printf("%d\n",n);
			continue ;
		}
		ll alive = n - ind + 1;
		last = x ;

		printf("%lld\n",alive) ;
	
	}
 
    return 0;
}


Comments

Submit
0 Comments
More Questions

1002. Find Common Characters
1602A - Two Subsequences
1555A - PizzaForces
1607B - Odd Grasshopper
1084A - The Fair Nut and Elevator
1440B - Sum of Medians
1032A - Kitchen Utensils
1501B - Napoleon Cake
1584B - Coloring Rectangles
1562B - Scenes From a Memory
1521A - Nastia and Nearly Good Numbers
208. Implement Trie
1605B - Reverse Sort
1607C - Minimum Extraction
1604B - XOR Specia-LIS-t
1606B - Update Files
1598B - Groups
1602B - Divine Array
1594B - Special Numbers
1614A - Divan and a Store
2085. Count Common Words With One Occurrence
2089. Find Target Indices After Sorting Array
2090. K Radius Subarray Averages
2091. Removing Minimum and Maximum From Array
6. Zigzag Conversion
1612B - Special Permutation
1481. Least Number of Unique Integers after K Removals
1035. Uncrossed Lines
328. Odd Even Linked List
1219. Path with Maximum Gold